1. Field of the Invention
The present invention relates to a method for managing a content addressable memory (CAM) look-up table using the longest prefix matching (LPM), and more particularly, to a method for adding data to the CAM look-up table using LPM, the apparatus therefor and recording medium therefor.
2. Description of the Related Art
FIG. 1 is a block diagram of a forwarding engine 110 for routing by a conventional router. The forwarding engine 110 extracts a destination address from an incoming IP packet 100. Then, a next hop determination unit 120 finds out a next hop (not shown) for the destination address of the IP packet 100, referring to information regarding the next hop stored in a forwarding table 130, and then transmits the IP packet 100 to the next hop.
Here, the longest prefix that matches the destination address of the incoming packet is generally searched to find the next hop using the destination address of the IP packet 100. There are a lot of methods for realizing the longest prefix matching (LPM).
The LPM can be searched using a tree, which is a modified binary tree, as shown in FIG. 2. Here, nodes 210 through 240 are nodes corresponding to 0* prefix of a forwarding table, 10* prefix, 111* prefix and 11010* prefix, respectively. However, with such a tree structure of FIG. 2, it does not take uniform time to search the LPM using a destination address of an IP packet. In other words, the LPM can be directly searched when a prefix that matches destination address is 1-bit long. However, when a prefix that matches a destination address is n-bit long, the LPM is searched by comparing the prefixes n times.
To solve such a problem, a method for searching the LPM using a specific memory such as a content addressable memory (CAM) has been suggested. When data containing destination addresses is input to the CAM, a destination address matching the LPM is output. If there are at least two addresses matching the LPM, the CAM outputs the lower address out of these addresses. FIG. 3 is a view of a forwarding table 300 in which prefix and next hop data is stored. For instance, if a destination address included in a packet is “103.23.122.7”, a next hop stored in the lowest address among addresses having the same prefix length, which are stored in the forwarding table 300, is extracted, i.e., 107.3.2.22.
Therefore, there is a need to store data in a look-up table of the CAM, which is a forwarding table, from the lowest address in the longest prefix length order. Also, it is required an easy and efficient method of adding new data into the look-up table of the CAM.